package leetcode.hot100;

public class number53 {
    public static void main(String[] args) {
        System.out.println(maxSubArray(new int[]{5,4,-1,7,8}));
    }
    public static int maxSubArray(int[] nums) {
        int maxSum=Integer.MIN_VALUE;
        int sum=0;
        int left=0,right=0;
        int maxLower=Integer.MIN_VALUE;
        while(right<nums.length){
            maxLower=Math.max(maxLower,nums[right]);
            if(sum+nums[right]<0){
                left++;
                right=left;
                sum=0;
            }else{
                sum+=nums[right];
                right++;
                maxSum=Math.max(maxSum,sum);
            }
        }
        return maxSum==Integer.MIN_VALUE?maxLower:maxSum;
    }
}
